<!DOCTYPE html>
<html lang="en">
  <head>
    
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="icon" type="image/svg+xml" href="img/elk_fav.svg">

    
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">
    <link rel="stylesheet" href="https://www.eclipse.org/elk/css/elk.css">
    <link rel="stylesheet" href="https://www.eclipse.org/elk/css/prism.css">

    <title>Rectpacking (Updated) (ELK)</title>

    
    
  </head>
  <body>

<nav class="navbar navbar-expand-lg navbar-dark">
  <button class="navbar-toggler navbar-toggler-right" type="button" data-toggle="collapse" data-target="#navbarCollapse" aria-controls="navbarCollapse" aria-expanded="false" aria-label="Toggle navigation">
    <span class="navbar-toggler-icon"></span>
  </button>
  <a class="navbar-brand" href="https://www.eclipse.org/elk/">
    <img src="img/elk_small_light.svg" height="30" class="d-inline-block align-top mr-1" alt="">
    Eclipse Layout Kernel&trade;
  </a>
  <div class="collapse navbar-collapse" id="navbarCollapse">
    <ul class="navbar-nav mr-auto">

      
      
        
        <li class="nav-item">
          <a class="nav-link" href="../../../downloads.html">Downloads</a>
        </li>
      
        
        <li class="nav-item">
          <a class="nav-link" href="../../../gettingstarted.html">Getting Started</a>
        </li>
      
        
        <li class="nav-item">
          <a class="nav-link" href="../../../documentation.html">Documentation</a>
        </li>
      
        
        <li class="nav-item">
          <a class="nav-link" href="../../../reference.html">Reference</a>
        </li>
      
        
        <li class="nav-item">
          <a class="nav-link" href="../../../support.html">Support</a>
        </li>
      
        
        <li class="nav-item active">
          <a class="nav-link" href="../../../blog.html">Blog Posts <span class="sr-only">(current)</span></a>
        </li>
      

      <li class="nav-item">
        <a class="nav-link" href="https://github.com/eclipse-elk/elk">GitHub</a>
      </li>

    </ul>
  </div>
</nav>


<div class="container px-3 py-5">


<div class="row">
  <div class="col-sm-9">
    <h1>Rectpacking (Updated)</h1>

    <p><em>By Sören Domrös, August 31, 2022</em>, updated January 4, 2024</p>
<p>The <a href="https://www.eclipse.org/elk/reference/algorithms/org-eclipse-elk-rectpacking.html"><code>rectpacking</code></a> algorithm was introduced to solved common problems with the <a href="https://www.eclipse.org/elk/reference/algorithms/org-eclipse-elk-box.html"><code>box</code></a> algorithm, which cannot stack boxes in a row.
The idea is to form stacks with subrows inside rows, while the size of a row is always dominated by a highest rectangle to provide a visual anchor point to &ldquo;read&rdquo; the rows from left to right.</p>
<p>Since it was a common use case of the <code>box</code> algorithm to add a priority to order the rectangles rectpacking uses the model order (which corresponds to the input order of the rectangles) as a criterion.
By enabling <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-interactive.html">interactive layout</a> and setting <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-desiredPosition.html">desired positions</a> for nodes, this order can be changed without changing the order in the input graph.</p>
<p>Box algorithm:</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-box-noexpand-annotated.svg"
    
     alt="Example graph with box algorithm."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<p>Rectpacking algorithm:</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-subrows-annotated.svg"
    
     alt="Better layout with rectpacking by using subrows inside rows."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<h2 id="algorithm">Algorithm</h2>
<p>The algorithm is divided into several phases.</p>
<h3 id="width-approximation">Width approximation</h3>
<p>Same as the <code>box</code> algorithm <code>rectpacking</code> packs rectangles inside a given aspect ratio.
As a first step this problem is transformed in a strip packing problem by approximating the width.</p>
<p>The width can also be specified by setting a <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-targetWidth.html">target width</a> ) (ELK 0.9.0 <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-widthApproximation-targetWidth.html">target width</a>).</p>
<p>Different strategies can be chosen for width approximation based on which <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-optimizationGoal.html">goal</a> (ELK 0.9.0 <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-widthApproximation-optimizationGoal.html">goal</a>) the greedy algorithm should prioritize.</p>
<p>Since the approximated width is mainly responsible for the line breaks between the rows that are formed by rectpacking, one can make sure that a rectangle is placed <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-inNewRow.html">in a new row</a> (since ELK 0.9.0).</p>
<p><code>GREEDY</code> <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-widthApproximation-strategy.html">width approximation</a> (0.9.0) may yield the following graph:</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-widthapproximation-annotated.svg"
    
     alt="Graph after width approximation."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<h3 id="placement">Placement</h3>
<p>Rectangles are placed in rows similar to the <code>box</code> algorithm. Per default the row height does not change after this step. By enabling <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-packing-compaction-rowHeightReevaluation.html">row height re-evaluation</a> (since ELK 0.9.0) the row height might change by investing more computation time. After placement the graph looks like this:</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-placement-annotated.svg"
    
     alt="Graph after initial placement."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<h3 id="compaction">Compaction</h3>
<p>After placement the rectangles are compacted to from stack with subrows inside the rows. This can also be <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-rowCompaction.html">disabled</a> (ELK &lt; 0.9.0), however, this is not recommended.</p>
<p>In ELK 0.9.0 this step is part of the placement step and done via the default <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-packing-strategy.html"><code>packing.strategy</code></a>. Only placement can be done by setting the <code>packing.strategy</code> to <code>SIMPLE</code>.</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-rectpacking-noexpand-annotated.svg"
    
     alt="graph after compaction."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<h3 id="whitespace-elimination">Whitespace Elimination</h3>
<p>Rectangles can <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-expandNodes.html">fill potential whitespace</a> (ELK 0.9.0 <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-whiteSpaceElimination-strategy.html"><code>whiteSpaceElimination.strategy</code></a> set to <code>EQUAL_BETWEEN_STRUCTURES</code>).</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-rectpacking-annotated.svg"
    
     alt="graph after whitespace elimination."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>

<p>The drawing can also be configured to fill whitespace such that the drawing has the <a href="https://www.eclipse.org/elk/reference/options/org-eclipse-elk-rectpacking-expandToAspectRatio.html">desired aspect ratio</a> (ELK 0.9.0 .  <a href="https://eclipse.dev/elk/reference/options/org-eclipse-elk-rectpacking-whiteSpaceElimination-strategy.html"><code>whiteSpaceElimination.strategy</code></a> set to <code>TO_ASPECT_RATIO</code>).</p>
<p>
  <img
    class="img-fluid"
    
      src="../../../img/scchartsregions-rectpacking-toaspectratio2.svg"
    
     alt="Whitespace eliminated to fit the aspect ratio."
    style = "max-height: 500px; display: block;
    margin-left: auto;
    margin-right: auto;"
  />
</p>


  </div>

  <div class="secnav col-sm-3">
  <ul>
    
    
      
    
      
    
      
    
      
    
      
    
      
        




  
  <a href="../../../blog/2022.html">
    <li class="navlevel-1">
      2022
    </li>
  </a>
  
    
    




  
  <a href="../../../blog/posts/2022/22-08-31-rectpacking.html">
    <li class="navlevel-2 active">
      Rectpacking (Updated)
    </li>
  </a>
  

  
  <a href="../../../blog/posts/2022/22-11-17-libavoid.html">
    <li class="navlevel-2">
      Edge Routing with Libavoid
    </li>
  </a>
  


  

  
  <a href="../../../blog/2023.html">
    <li class="navlevel-1">
      2023
    </li>
  </a>
  
    
    




  
  <a href="../../../blog/posts/2023/23-01-09-constraining-the-model.html">
    <li class="navlevel-2">
      Layered: Constraining the Model
    </li>
  </a>
  

  
  <a href="../../../blog/posts/2023/23-04-11-topdown-layout.html">
    <li class="navlevel-2">
      Top-down Layout: Zoom in the Layout Process
    </li>
  </a>
  


  

  
  <a href="../../../blog/2024.html">
    <li class="navlevel-1">
      2024
    </li>
  </a>
  
    
    




  
  <a href="../../../blog/posts/2024/24-12-06-layer-unzipping.html">
    <li class="navlevel-2">
      Layered: Layer Unzipping
    </li>
  </a>
  


  

  
  <a href="../../../blog/2025.html">
    <li class="navlevel-1">
      2025
    </li>
  </a>
  
    
    




  
  <a href="../../../blog/posts/2025/25-08-21-layered.html">
    <li class="navlevel-2">
      Layered (overview)
    </li>
  </a>
  

  
  <a href="../../../blog/posts/2025/25-08-22-node-labels.html">
    <li class="navlevel-2">
      Node Labels
    </li>
  </a>
  


  


      
    
  </ul>

  <div class="incubation-egg">
    <a href="https://www.eclipse.org/projects/what-is-incubation.php">
      <img src="https://www.eclipse.org/images/egg-incubation.png" alt="Incubation" />
    </a>
  </div>
</div>

</div>

    </div>
    <footer role="contentinfo" class="footer">
      <div class="container">
        <div class="row">
            <div class="col">
              <span class="hidden-print">
                <a href="https://www.eclipse.org"><img class="logo-eclipse-white img-responsive" alt="logo" src="../../../img/eclipse_foundation_logo.svg"/></a>
              </span>
            </div>
            <div class="col">
              
            </div>
          </div>
        <div class="row">
          <div class="col hidden-print">
            <a href="http://www.eclipse.org/">Eclipse Foundation</a><br/>
            <a href="http://www.eclipse.org/legal/privacy.php">Privacy Policy</a><br/>
            <a href="http://www.eclipse.org/legal/termsofuse.php">Website Terms of Use</a><br/>
            <a href="http://www.eclipse.org/legal/copyright.php">Copyright Agent</a><br/>
            <a href="http://www.eclipse.org/legal">Legal</a>
          </div>
          <div class="col">
              <p class="copyright-text">Copyright &copy; Eclipse Foundation, Inc. All Rights Reserved.</p>
          </div>
        </div>
      </div>

    </footer>

    <script src="https://code.jquery.com/jquery-3.1.1.slim.min.js" integrity="sha384-A7FZj7v+d/sdmMqp/nOQwliLvUsJfDHW+k9Omg/a/EheAdgtzNs3hpfag6Ed950n" crossorigin="anonymous"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/tether/1.4.0/js/tether.min.js" integrity="sha384-DztdAPBWPRXSA/3eYEEUWrWCy7G5KFbe8fFjk5JAIxUYHKkDx6Qin1DkWx51bBrb" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.0.0/js/bootstrap.min.js" integrity="sha384-JZR6Spejh4U02d8jOt6vLEHfe/JQGiRRSQQxSfFWpi1MquVdAyjUar5+76PVCmYl" crossorigin="anonymous"></script>
    <script src="https://www.eclipse.org/elk/js/prism.js"></script>

    
    <script>$(function() { $('table').addClass('table'); })</script>
  </body>
</html>
